AD7·智能优化算法 — SA·GA·ACO·PSO 完整讲义

SIMULATED ANNEALING

一、模拟退火算法 (SA)

灵感来源：金属退火工艺。将金属加热至高温后缓慢冷却，原子从高能无序态逐步排列到低能有序的晶体结构。SA 将这一物理过程抽象为优化算法——目标函数类比为能量，全局最优解类比为能量最低的晶体态。

2.1 详细原理

Metropolis 接受准则——SA 的核心引擎

SA 区别于贪心搜索的关键在于：即使新解比当前解更差，仍以一定概率接受它。这个概率由 Metropolis 准则给出：

若 Δf = f(x_new) - f(x_current) < 0（新解更优）：确定接受
若 Δf ≥ 0（新解更差）：以概率 P = e^{-Δf / T} 接受

解释：温度 T 越高，e^-Δf/T 越接近 1，接受差解的概率越大（"乱撞"）；温度 T 越低，概率越接近 0（"精细搜索"）。这个从"广泛探索"到"逐步收敛"的动态过程，是 SA 跳出局部最优的根本机制。

温度 T 高时

• P ≈ 1：几乎接受所有新解
• 搜索范围大，全局探索为主
• 类似金属原子剧烈热运动
• 有机会跨越势垒逃离局部极小

温度 T 低时

• P → 0：几乎只接受改进解
• 搜索范围小，局部精细搜索
• 类似原子排列趋于稳定
• 在当前最优附近微调

降温策略——决定探索深度的关键

策略	公式	特点	适用
指数降温	T_k+1 = α·T_k，α∈(0.85,0.99)	前期降得慢，后期降得快	最常用（PPT采用α=0.995）
线性降温	T_k = T₀ - k·(T₀-T_f)/N	均匀下降，简单	小规模问题
对数降温	T_k = T₀ / ln(1+k)	极慢下降，理论收敛保证	理论分析，实际偏慢

新解构造方式——以 TSP 为例

2-opt（2-交换法）
随机选两个城市 u<v，将 u~v 之间的路径反转。
例：[1,5,3,8,2,6,7] → 反转5~2 → [1,2,8,3,5,6,7]

3-opt（3-交换法）
随机选三个城市 u<v<w，交换三段路径的顺序。
有4种可能的交换方式，选择最优者。

2.2 适用场景

场景类别	典型问题	SA 适用度	说明
组合优化	TSP、车间调度、装箱问题	最佳	离散解空间，SA 的邻域搜索天然适合
多目标优化	Pareto 前沿搜索	良好	可同时优化多个目标函数
连续函数优化	Ackley、Rastrigin 函数	可用	需设计合适的邻域扰动方式
VLSI 布局	芯片元件摆放、布线	最佳	经典应用，SA 最早就是用于 VLSI 设计
神经网络	超参数调优、权重初始化	良好	比 Grid Search 更高效
路径规划	机器人路径、物流配送	最佳	天然适合，常用 2-opt 邻域

2.3 典型案例：100 城市 TSP 求解

问题：飞机从基地(70°E,40°N)出发，以 1000 km/h 速度侦察 100 个目标后返回。求最短飞行路线。

案例步骤推演

1距离矩阵计算
102 个点（含基地出发和返回），用球面距离公式：
d = 6370·arccos(cosΔλ·cosφ₁·cosφ₂+sinφ₁·sinφ₂)

2初始解构造
随机生成 10000 个 TSP 回路，选最短者作为初始解 path₀

3迭代搜索
每轮迭代：随机 2-opt 产生新解 → 计算 Δf → Metropolis 判定 → 接受或拒绝 → T=T·α 降温

4结果
L_T=1000: 路径 39335.6，39.34h
L_T=10: 路径 42470.9，42.47h

📊 点击展开：参数敏感性实验详情

参数组	T₀	α	T_f	L_T	最优路径	时间	评价
组一（优）	10³	0.995	10⁻¹²	1000	39335.6	123s	质量高，时间长
组二（快）	10³	0.995	10⁻¹²	10	42470.9	1.7s	速度快，质量降

⚠ 关键发现：L_T（每温度采样次数）从 1000 降至 10，路径长度增加约 8%，但时间缩短 98%。在实际工程中需要在"解质量"与"计算时间"之间权衡。

2.4 🎯 学后检测（3 题）

1. 模拟退火算法中，Metropolis 准则的核心设计意图是什么？

2. SA 求解 TSP 时，L_T（每温度迭代次数）从 1000 降到 10 会导致什么？

3. SA 中降温系数 α 越接近 1（如 0.995），意味着什么？

GENETIC ALGORITHM

二、遗传算法 (GA)

灵感来源：达尔文自然选择 + 孟德尔遗传学。种群中适应度高的个体有更高概率存活和繁殖，通过基因的交叉重组和随机变异，后代逐步进化出更适应环境的特征。

2.1 详细原理

编码方式——连接问题与算法的桥梁

编码类型	表示方式	适用问题	优点	缺点
二进制编码	01001101...	背包、特征选择	编码/解码简单，交叉变异方便	难以表达解特征，精度有限
整数编码	[1,5,3,8,2,6,7,4]	TSP、调度排序	表达简单，天然适合排列问题	需专门设计交叉/变异算子
浮点数编码	[2.35,-1.67,4.02]	连续函数优化	精度高，适合大范围搜索	交叉变异需限制范围

选择算子——四种策略对比

① 轮盘赌选择
个体被选概率 ∝ 适应度。
优：实现自然选择
缺：低适应度个体可能被完全淘汰
适用：大规模种群

② 联赛选择
随机选 k 个个体比较，最优者胜出。
优：避免优秀个体早期被淘汰
缺：选择过程复杂
适用：需保持多样性的情况

③ 排序选择
按适应度从高到低排序，优先选高位。
优：最高适应度个体必被选，收敛快
缺：易导致早熟，减少多样性
适用：快速收敛场景

④ 随机竞争选择
随机选染色体对比较，适应度高者胜。
优：简单，保持一定多样性
缺：可能淘汰相对较好个体
适用：需保持多样性的种群

交叉算子

单点交叉
随机一点切断，交换两段
父：[A|BCD] × [E|FGH] → 子：[A|FGH]

两点交叉
两点间片段交换，比单点更灵活

算术交叉
子代 = λ·父₁ + (1-λ)·父₂
适合连续变量

为什么 TSP 中 pc=pm=1？——特殊结构的启示

关键洞察：TSP 要求每个城市恰好访问一次并返回起点。这种"排列约束"使得即使 100% 交叉和 100% 变异，产生的子代也天然有效（不会出现访问同一城市两次的情况）。因此可以将两个概率都设为 1，在每一代中最大程度地探索解空间。但注意：这并非 GA 的通用设置——在其他问题中 pc 通常取 0.4~0.9，pm 取 0.001~0.1。

2.2 适用场景

场景类别	典型问题	GA 适用度	说明
复杂非线性优化	多峰函数、不可微函数	最佳	不依赖梯度，天然适合黑箱优化
TSP/VRP	旅行商、车辆路径	最佳	整数编码+交叉变异天然适合排列问题
特征选择	高维数据降维	最佳	二进制编码"选/不选"特征
神经网络结构搜索	NAS（神经架构搜索）	良好	可编码网络层数和节点数
参数优化	PID调参、机械设计	良好	浮点数编码，多目标优化
调度问题	车间作业、考试安排	最佳	整数编码，天然适合排序调度

2.3 典型案例：GA 求解 TSP

1初始种群
随机生成 1600 个 TSP 回路，每个经 3 轮 2-opt 局部优化，确保初始种群质量

2交叉产子
随机配对父代 → 单点交叉 → 产生 1600 个子代 A

3变异探索
每个个体进行 5 次随机变异(3~10-opt)，选最优 → 1600 个变异体 B

4精英选择
从父代 J + 子代 A + 变异体 B = 4800 个中，选前 1600 进入下一代

5结果
最优路径 39355 | 耗时 42.8s | 侦察时间 39.2~39.5h

📊 点击展开：为什么 pc=pm=1 对 TSP 有效？详细论证

1. TSP 结构保证有效性：排列编码下，单点交叉产生的子代仍然是合法排列（从中断点取父1前半 + 父2去掉父1前半已用城市后剩下的）。不会出现"访问同一城市两次"。

2. 变异打破局部最优：3~10-opt 随机变异是 TSP 领域已知的强局部搜索算子，保证每个个体都有机会逃离当前局部最优。

3. 精英选择兜底：父+子+变异三代竞争，即使交叉变异产生劣解，精英选择也会淘汰它们。确保了"只会进步，不会退步"。

4. 数值实验验证：PPT 中 50 代后收敛到 39.2h 以内，证明了此策略的有效性。

2.4 🎯 学后检测（3 题）

1. GA 中轮盘赌选择遵循什么原则？

2. TSP 问题适合采用哪种编码方式？为什么？

3. GA 中变异操作的主要目的是什么？

ANT COLONY OPTIMIZATION

三、蚁群算法 (ACO)

灵感来源：蚂蚁觅食的群体智能。单只蚂蚁的行为是随机的，但蚁群通过释放信息素（pheromone）实现自组织——经过路径的蚂蚁越多，信息素越浓，后续蚂蚁越倾向于跟随，最终形成最短路径。1992 年 Marco Dorigo 博士论文首次提出。

3.1 详细原理

信息素机制——ACO 的灵魂

正反馈（Positive Feedback）
好路径 → 更多蚂蚁走 → 更多信息素 → 更吸引蚂蚁 → 更强化。这是 ACO 收敛到最优解的根本驱动力。

信息素挥发（Evaporation）
每轮迭代，所有边上的信息素乘以 (1-ρ)。挥发因子 ρ 通常在 0.05~0.5。ρ 太小 → 残留信息素误导后续蚂蚁（过早收敛）；ρ 太大 → 信息素来不及积累（随机游走）。

蚂蚁路径选择——概率公式详解

蚂蚁 k 从城市 i 转移到城市 j 的概率：
P_ij^k = τ_ij^α · η_ij^β / Σ_{l∈允许集}(τ_il^α · η_il^β)

符号	含义	PPT 取值	作用
τ_ij	边(i,j)的信息素浓度	初始全为 1	反映群体经验——走过的蚂蚁越多，浓度越高
η_ij = 1/d_ij	能见度（启发信息）	距离的倒数	反映局部贪心——越近的城市越有吸引力
α	信息素重要因子	1	α 越大，越依赖群体经验（跟随蚁群）
β	能见度重要因子	5	β 越大，越依赖局部距离（贪心选择）
ρ	信息素挥发因子	0.1	每轮保留 90% 旧信息素

PPT 中 α=1, β=5 的含义：能见度的权重是信息素的 5 倍。这意味着蚂蚁在选择下一个城市时，首先看重距离最近的，其次才参考群体留下的信息素。这种"贪心+群体引导"的平衡策略在实践中效果很好。

连续优化中的 ACO 适配

组合优化中信息素记录在边上（相邻两点之间）；连续优化中信息素留存在蚂蚁经过的点上，影响该点附近区域。搜索方式从"离散跳跃"变为"小步快走"——每个蚂蚁移动前先进行 10 次局部随机探测，选择最好的方向前进。全局搜索系数 1/√T 和局部搜索半径 2/T² 随迭代次数 T 自适应衰减。

3.2 适用场景

场景类别	典型问题	ACO 适用度	说明
TSP / VRP	旅行商、车辆路径规划	最佳	ACO 最经典的应用领域
网络路由	通信网络、物流配送	最佳	蚂蚁=数据包，信息素=链路质量
资源调度	机器调度、云计算资源分配	最佳	天然适合"分配问题"
连续函数优化	Ackley、Griewank 等	良好	需适配：信息素从边上改为点上
图像分割	聚类、边缘检测	可用	蚂蚁在图像上移动，信息素标记区域

3.3 典型案例：ACO 求解 100 城市 TSP + Ackley 函数

案例 A：TSP

1初始化
100 只蚂蚁 | α=1, β=5, ρ=0.1 | 信息素矩阵全 1 | 1000 轮迭代

2路径构建
每只蚂蚁从随机城市出发，用概率公式选择下一城市，禁忌表排除已访问城市

3局部优化
每只蚂蚁完成 TSP 后，执行 20 轮 2-opt 局部改进

4信息素更新
τ ← 0.9τ + Σ(1/路径长度)，更好的路径留下更多信息素

5结果
最短 39284 | 耗时 ~520s | 比 SA(39336) 和 GA(39355) 略优

案例 B：Ackley 函数连续优化

问题：求 Ackley 函数在 [-5,5]² 上的最小值（全局最优 = 0，位于 (0,0)）。Ackley 函数表面密布局部极小值，极难优化。

1编码
每个蚂蚁 = 二维坐标 (x,y) | 随机分布在搜索区域

2局部搜索
蚂蚁以概率 P₀=4T/(5T+15) 进行局部搜索：从前轮最优 10 个方向中选一个，移动 lamda=2/T² 步长

3全局搜索
以概率 1-P₀ 进行全局随机搜索，步长 ∝ 1/√T

4结果
100 只蚂蚁 × 100 轮 | 最优值 -0.00029 | 耗时 0.997s | 几乎接近理论值 0

3.4 🎯 学后检测（3 题）

1. ACO 中信息素挥发因子 ρ 的核心作用是什么？

2. 蚂蚁选择下一城市的概率由哪两大核心因素共同决定？

3. ACO 求解连续优化问题时，与求解 TSP 最大的不同是什么？

PARTICLE SWARM OPTIMIZATION

四、粒子群算法 (PSO)

灵感来源：鸟群觅食的群体行为。每只鸟只知道自己离食物多远、以及群体中最靠近食物的那只鸟的位置——但它不知道食物究竟在哪。通过结合"自己的经验"和"群体的信息"，整个鸟群逐步收敛到食物位置。

4.1 详细原理

速度-位移模型——PSO 的核心引擎

速度更新：v_i^k+1 = ω·v_i^k（惯性）+ c₁r₁(p_i^k-x_i^k)（认知）+ c₂r₂(p_g^k-x_i^k)（社会）
位置更新：x_i^k+1 = x_i^k + v_i^k+1

速度公式三项深度解析

🟢 惯性项 ω·vᵏ
保持当前飞行方向。
ω 大 → 大步搜索，利于全局探索
ω 小 → 小步微调，利于局部精细
典型设置：0.9 线性递减至 0.4

🟢 认知项 c₁r₁(pᵢ-xᵢ)
"自我学习"——向自己历史最优位置靠近。
c₁ 大 → 每个粒子更独立，但收敛慢
c₁=0 → 只有社会学习，易早熟

🟢 社会项 c₂r₂(p_g-xᵢ)
"社会学习"——向群体最优靠近。
c₂ 大 → 快速向群体最优聚集
c₂=0 → 各粒子独立搜索，退化

关键参数详解

参数	含义	典型值	过大	过小
ω	惯性权重	0.9→0.4（递减）	粒子"乱飞"，不收敛	快速停下来，陷入局部最优
c₁	认知学习因子	2.0	粒子过度独立，收敛慢	缺乏自我探索，过度依赖群体
c₂	社会学习因子	2.0	过早聚集，多样性丧失	群体信息利用不足
v_max	最大速度	搜索空间宽度的 10%~20%	可能飞过最优解	搜索范围受限
m	种群大小	20~40（简单）/ 100~200（困难）	计算量增大，收益递减	多样性不足

PSO vs GA：核心差异

PSO 粒子群
• 粒子有"记忆"——保留个体历史最优
• 速度-位移模型直接迭代
• 没有"死亡"——所有粒子存活到结束
• 信息单向流动（只从最优流向其他）
• 收敛快，实现简单

GA 遗传算法
• 个体无"记忆"——只看当前适应度
• 选择+交叉+变异三代操作
• 个体有"生死"——差适应度被淘汰
• 信息双向交换（交叉操作）
• 收敛较慢，但全局搜索更强

4.2 适用场景

场景类别	典型问题	PSO 适用度	说明
连续函数优化	Schaffer、Rastrigin 等多峰函数	最佳	PSO 的天然优势领域
工程参数优化	PID 控制器、机械设计参数	最佳	PPT 中非线性约束优化案例即此类
神经网络训练	权重优化、超参数调优	良好	比反向传播更不易陷入局部最优
电力系统优化	最优潮流、机组组合	最佳	多约束、高维度场景
组合优化	TSP、调度	可用	需离散化适配（如 BPSO）

4.3 典型案例

案例 A：Schaffer 函数优化

问题：求 f(x,y) = 0.5 + (sin²(√(x²+y²))-0.5) / (1+0.001(x²+y²))² 在 [-4,4]² 上的最小值。理论最优 = -1，位于 (0,0)。但该函数有无穷多个局部极小值（值 ≈ -0.99），极易陷入。

1参数设置
80 粒子 | 200 迭代 | ω=0.5 | c₁=c₂=2.0 | v_max=1

2初始化
粒子随机分布在 [-4,4]² 内，随机初始速度

3自适应变异
rand>0.8 时随机改变某维位置——防止陷入无穷局部极小值环

4结果
近似最优值 -1.0 | 最优点接近 (0,0) | 耗时 0.21s | 极快极准

案例 B：非线性约束优化——焊接梁设计

问题（PPT 例 6）：设计焊接梁的四个参数 x₁~x₄，在满足剪切应力、弯曲应力、屈曲载荷、挠度等 7 个约束的条件下，最小化制造成本。

1罚函数处理
将约束条件以罚函数形式加入目标函数，PSO 无需单独处理可行性

2自适应 PSO
30 粒子 | 150 迭代 | 随机衰减因子 0.95 | 惯性因子自适应调整

3结果
最优成本 1.7346 | 最优参数 (0.199, 3.617, 9.037, 0.206) | 耗时 0.21s

4.4 🎯 学后检测（3 题）

1. PSO 速度公式中惯性因子 ω 的主要作用是？

2. PSO 与 GA 相比，最本质的区别是什么？

3. PPT 中 Schaffer 函数优化案例，为避免 PSO 陷入局部最优采用了什么策略？

COMPARISON

五、四种智能优化算法综合对比

维度	SA 模拟退火	GA 遗传算法	ACO 蚁群算法	PSO 粒子群
灵感	金属退火	自然进化	蚂蚁觅食	鸟群觅食
搜索方式	单点迭代（独狼）	种群并行	种群并行	种群并行
核心机制	Metropolis 概率接受	选择+交叉+变异	信息素正反馈+挥发	速度-位移模型
关键参数	T₀, α, Tf, L_T	M, G, pc, pm	m, α, β, ρ	m, ω, c₁, c₂, vmax
逃离局部最优	概率接受差解	变异+种群多样性	信息素挥发+随机选择	惯性+自适应变异
适合问题	组合优化、多目标	复杂非线性、多模态	TSP、路由、调度	高维连续、工程优化
实现难度	★ 简单	★★★ 复杂	★★ 中等	★ 简单
收敛速度	★★ 中等	★ 较慢	★ 较慢	★★★ 快

选择指南

TSP / 路径规划：ACO > SA > GA。ACO 信息素机制天然适合图搜索；SA 的邻域搜索也很高效；GA 虽可用但需精心设计算子。
连续函数优化：PSO > GA > SA。PSO 收敛最快，参数最少；GA 浮点编码也有效；SA 需适配邻域定义。
多约束工程问题：PSO（罚函数）+ GA（多目标）。PSO 快但处理约束需外挂罚函数；GA 天然支持多目标优化。
需要快速原型：PSO 或 SA。两者实现最简单，参数最少。PSO 更适合连续问题，SA 更适合离散问题。